/*
*
给你一个由字符 'a'、'b'、'c' 组成的字符串 s 和一个非负整数 k 。每分钟，你可以选择取走 s 最左侧 还是 最右侧 的那个字符。

你必须取走每种字符 至少 k 个，返回需要的 最少 分钟数；如果无法取到，则返回 -1 。

示例 1：

输入：s = "aabaaaacaabc", k = 2
输出：8
解释：
从 s 的左侧取三个字符，现在共取到两个字符 'a' 、一个字符 'b' 。
从 s 的右侧取五个字符，现在共取到四个字符 'a' 、两个字符 'b' 和两个字符 'c' 。
共需要 3 + 5 = 8 分钟。
可以证明需要的最少分钟数是 8 。
示例 2：

输入：s = "a", k = 1
输出：-1
解释：无法取到一个字符 'b' 或者 'c'，所以返回 -1 。

提示：

1 <= s.length <= 105
s 仅由字母 'a'、'b'、'c' 组成
0 <= k <= s.length

  - @author ala
  - @date 2024-09-27 11:56
*/
package main

import "fmt"

func main() {
	//s, k := "aabaaaacaabc", 2
	//s, k := "a", 1
	s, k := "caaababcaa", 2

	fmt.Println(takeCharacters(s, k))
}

/**
 *	1）滑窗，维护窗口外部每个字母的数量
 *	2）取最大滑窗，答案 = 长度 - 最大滑窗
 */
func takeCharacters(s string, k int) int {
	N := len(s)
	if N < k*3 {
		return -1
	}

	cnts := [3]int{}
	for i := 0; i < N; i++ {
		cnts[s[i]-'a']++
	}
	if cnts[0] < k || cnts[1] < k || cnts[2] < k {
		return -1
	}

	mx := 0
	for l, r := 0, -1; r < N-1; {
		r++
		c := s[r] - 'a'
		cnts[c]--
		for l <= r && cnts[c] < k {
			cnts[s[l]-'a']++
			l++
		}
		mx = max(mx, r-l+1)
	}
	return N - mx
}
